// 2025/07/25
// Author: Forever
#include <bits/stdc++.h>
using namespace std;
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& vec)
{
    os << "["; 
    bool first = true;
    for (const auto& item : vec) {
        if (!first)
            os << ", "; 
        os << item;
        first = false;
    }
    os << "]"; 
    return os;
}
template <typename A, typename B>
ostream& operator<<(ostream& os, const pair<A, B>& p)
{
    os << "(" << p.first << ", " << p.second << ")";
    return os;
}
template <typename A, typename B>
ostream& operator<<(ostream& os, const map<A, B>& m)
{
    os << "{";
    bool first = true;
    for (const auto& p : m) {
        if (!first)
            os << ", ";
        os << p.first << ": " << p.second;
        first = false;
    }
    os << "}";
    return os;
}
template <typename A, typename B>
ostream& operator<<(ostream& os, const unordered_map<A, B>& m)
{
    os << "{";
    bool first = true;
    for (const auto& p : m) {
        if (!first)
            os << ", ";
        os << p.first << ": " << p.second;
        first = false;
    }
    os << "}";
    return os;
}
#define error(args...)                           \
    {                                            \
        string _s = #args;                       \
        replace(_s.begin(), _s.end(), ',', ' '); \
        stringstream _ss(_s);                    \
        istream_iterator<string> _it(_ss);       \
        cout << "-----DEBUG-----" << endl;     \
        err(_it, args);                          \
        cout << "------END------" << endl;     \
    }
void err(istream_iterator<string> it) { }
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args)
{
    cout << *it << " = " << a << endl;
        err(++it, args...);
}
void setIO(string name = "")
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (!name.empty()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
}
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
int MOD;
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
ll quick_pow(ll base, ll exp, ll mod = MOD)
{
    ll res = 1;
    while (exp) {
        if (exp & 1) {
            res = res * base % mod;
        }
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}

ll C(ll n, ll m, ll mod = MOD){
    if (m == 0)
        return 1;
    if (n < m)
        return 0;
    ll ans = 1;
    for (int i = m + 1; i <= n; i++) 
        ans = ans * i % mod;
    for (int i = 1; i <= m; i++) 
        ans = ans * quick_pow(i, mod - 2, mod) % mod;
    return ans;
}

ll Lucas(ll n, ll m, ll mod = MOD){
    if (m == 0)
        return 1;
    return C(n % mod, m % mod, mod) * Lucas(n / mod, m / mod, mod) % mod;
}

signed main()
{
    setIO();
    int t;
    cin >> t;
    while (t--) {
        ll n, m;
        cin >> n >> m >> MOD;
        cout << Lucas(n, m) << '\n';
    }
    return 0;
}